package _18_剑指OfferII;

import java.util.*;

public class _114_剑指OfferII外星文字典 {

    public static void main(String[] args) {

        _114_剑指OfferII外星文字典 v = new _114_剑指OfferII外星文字典();


        String[] words = {"z", "z"};
        System.out.println(v.alienOrder(words));

    }


    public String alienOrder(String[] words) {
        // 当前点到某些点的集合
        List<Character>[] list = new ArrayList[26];
        // 当前边的入度集合
        int[] values = new int[26];
        Arrays.fill(values, -1);
        // 构造拓扑图集合
        if (!buildTopologic(words, list, values)) return "";

        Queue<Character> queue = new LinkedList<>();
        // 找到入度为0的集合
        for (int i = 0; i < values.length; ++i) {
            if (values[i] == 0) {
                queue.add((char) (i + 'a'));
            }
        }

        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            Character ele = queue.poll();
            sb.append(ele);
            values[ele - 'a'] = -1;
            ArrayList<Character> tos = (ArrayList<Character>) list[ele - 'a'];
            if (tos == null) continue;
            for (Character to : tos) {
                if (--values[to - 'a'] == 0) {
                    queue.add(to);
                }
            }
        }

        for (int value : values) {
            if (value != -1) {
                return "";
            }
        }
        return sb.toString();
    }

    // 构造拓扑图
    private boolean buildTopologic(String[] words, List<Character>[] list, int[] values) {
        int len = words.length;
        // 初始化数据
        for (String word : words) {
            for (int i = 0; i < word.length(); ++i) {
                if (values[word.charAt(i) - 'a'] == -1)
                    values[word.charAt(i) - 'a'] = 0;
            }
        }

        out: for (int i = 1; i < len; ++i) {
            int index1 = 0, index2 = 0;
            String cur = words[i], prev = words[i - 1];
            while (index1 < prev.length() && index2 < cur.length()) {
                char prevChar = prev.charAt(index1);
                char curChar = cur.charAt(index2);
                if (prevChar != curChar) {
                    // 已经找到字典序
                    if (list[prevChar - 'a'] == null) {
                        list[prevChar - 'a'] = new ArrayList<>();
                    }
                    list[prevChar - 'a'].add(curChar);
                    values[curChar - 'a']++;
                    // 跳出最外层循环
                    continue out;
                }
                index1++;
                index2++;
            }
            // 未找到字典序，但是不符合字典序的排序逻辑
            if (prev.length() >  cur.length()) return false;
        }
        return true;
    }

}
